package leetcode.method.dynamic_programming;

public class Program5WordLongestPalindrome {

    public Program5WordLongestPalindrome() {
    }

    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        // 二维矩阵标记从i~j的回文状况
        boolean[][] index = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            index[i][i] = true;
        }
        int maxLength = 1;
        int begin = 0;
        char[] sCharArray = s.toCharArray();
        // 设定回文长度
        for (int i = 2; i <= length; i++) {
            for (int start = 0; start < length; start++) {
                int end = start + i - 1;
                if (end == length) {
                    break;
                }

                if (sCharArray[start] != sCharArray[end]) {
                    index[start][end] =false;
                } else {
                    if (end - start < 3) {
                        index[start][end] = true;
                    } else {
                        index[start][end]  = index[start+1][end-1];
                    }
                }

                if (index[start][end] && end - start + 1 >maxLength ) {
                    maxLength = end - start + 1;
                    begin = start;
                }
            }
        }
        return s.substring(begin, begin + maxLength);

    }

    public static void main(String[] args) {
        Program5WordLongestPalindrome myStack = new Program5WordLongestPalindrome();
        System.out.println(myStack.longestPalindrome("babad"));
        System.out.println(myStack.longestPalindrome("cbbd"));
    }
}
